The advent of IPv6 makes it possible to connect to a network an apparatus which is conventionally unable to connect to a network. An example is an end-user digital camera which can be directly connected to the Internet.
A case in which an IPv6 communication apparatus performs cryptographic communication by using IPsec will be explained below.
IPsec is a protocol such that two apparatuses on the Internet sharing secret data unknown to anybody else perform encryption and authentication on the basis of this secret data. To communicate with each other, these two apparatuses must securely share the secret data, their IPv6 addresses, and the like. Data such as the secret data and IPv6 addresses is called SA (Security Association). A protocol by which SA is securely shared is called IKE (Internet Key Exchange), and defined in RFC2409 “The Internet Key Exchange (IKE)”. “Securely sharing SA” is to reliably share SA only with an intended partner, and requires reliable authentication of the partner. IKE uses the Diffie-Hellman public-key distribution scheme (to be referred to as DH hereinafter) as a secret data sharing method, and four authentication methods are defined.
Of processes performed during the execution of IKE, the process of DH has the heaviest load. In this process of DH, modular exponentiation of a large integer (e.g., 512 bits in around 1990, and desirably about 1,024 bits in recent years) particularly has a heavy load. Modular exponentiation is to calculate A which satisfies A=B^{C} mod D, i.e., calculate a residue A obtained by dividing BC by D, from B, C, and D. Note that B^{C} or BC mean B to the C-th power. When modular exponentiation is to be performed using a K-bit integer, K+(the number of 1's in the binary representation of the exponent C)−1 modular multiplications are necessary. If K is 512, 767 (=512+256−1) modular multiplications are necessary on average.
Apparatuses which communicate by IPv6 do not always have high computation capability like that of the end-user digital camera as described above. If such an apparatus executes IKE, the processing time may take a few minutes, so it is important to reduce this processing time. Note that not only IKE but many public-key cryptography such as DH, RSA cryptosystem, ElGamal encryption scheme, and ElGamal signature scheme require modular exponentiation. To use public-key cryptography, therefore, it is useful to efficiently execute modular exponentiation.
The inverse operation of this modular exponentiation is called the discrete logarithm problem, i.e., given a modulus D, a base B, and a number A, obtaining an exponent C such that A=B^C mod D. If the modulus is large, the discrete logarithm problem is practically unsolvable. This is (one of) the bases of the security of the public-key cryptography described above. As a mathematical setting for implementing DH, it is possible to use a multiplicative group of a finite field, or an elliptic curve over a finite field. Although the following explanation will be made by taking a multiplicative group as an example, the present invention is also effective when an elliptic curve is used.
Research and development are being made on a method by which an apparatus having low computation capability requests an apparatus having high computation capability to perform computations, while hiding secret information necessary for the computations (Tsutomu MATSUMOTO, Koki KATO, Hideki IMAI, “Smart cards can compute secret heavy functions with powerful terminals”, The 10th Symposium on Information Theory and Its Applications (1987), Tsutomu MATSUMOTO, Koki KATO, Hideki IMAI, “Speeding up secret computations with insecure auxiliary devices”, Advances in Cryptology—CRYPTO '88, pp. 497-506, Springer-Verlag (1988)). Such a method is referred to as server-aided computation (SAC for short), hereinafter.
As a practical example of SAC, RSA cryptosystem's secret transformation (decryption or signature generation) is most typical. In this method, an apparatus (client) having low computation capability has a secret key and requests an apparatus (server) having high computation capability to perform a modular exponentiation using the secret key as an exponent, without revealing the secret key to the server. The modulus is a composite number in RSA cryptosystem's secret transformation, and is a prime number in DH. However, the both are modular exponentiation using a secret key as an exponent.
A plurality of SAC methods for RSA cryptosystem's secret transformation are proposed, and these methods include methods applicable to modular exponentiation of DH. One of the methods (RSA-S1 to be described later) is based on the assumption that the discrete logarithm problem is infeasible and the security of the method is evaluated by the number of possible combinations when the method is broken by exhaustive search of possible combinations. When parameters are so determined that the number of possible combinations is about 10^20, RSA-S1 requires 20 modular multiplications.
Another SAC method for RSA cryptosystem's secret transformation is also proposed (U.S. Pat. No. 5,046,094).
Some of these methods are presumably applicable to modular exponentiation of DH. In these methods, computations performed by a client and computations performed by a server can be executed in parallel, thereby optimally reducing the total processing time even when the computation capabilities or communication line speeds are different. In these methods, a client also performs modular exponentiation. Therefore, if the method is broken by exhaustive search of possible combinations and the number of the possible combinations is about 10^20 (=approximately 2^67), the client must perform modular exponentiation using an exponent of about 67 bits. The average number of modular multiplication is about 100, which is larger than that in the method (RSA-S1) by MATSUMOTO et. al.
Still another SAC method for RSA cryptosystem's secret transformation is also proposed, and this method is presumably applicable to DH (U.S. Pat. No. 5,369,708).
The main purpose of this method is not to leak any secret information necessary for secret transformation, and the processing efficiency of the method is made higher than those of similar conventional methods. However, when the number of bits is 512, a client must perform 100 or more modular multiplication. This number is larger than that in the method (RSA-S1) by MATSUMOTO et. al.
The above SAC methods can be used to request one modular exponentiation.
In DH, however, a modular exponentiation is repeated twice as follows.
A protocol when entities A and B execute DH by using a prime p and a generator g as common parameters will be described below with reference to FIG. 4.
In step S401A, the entity A generates secret information x_A. In step S401B, the entity B generates secret information x_B.
In step S402A, the entity A computes y_A=g^(x_A) mod p. In step S403A, the entity A sends y_A to the entity B.
In step S402B, the entity B computes y_B=g^(x_B) mod p. In step S403B, the entity B sends y_B to the entity A.
In step S404A, the entity A computes y_AB=(y_B)^(x_A) mod p. In step S404B, the entity B computes y_BA=(y_A)^(x_B) mod p.
Since y_AB=(g^(x_B))^(x_A) mod p=g^(x_A*x_B) mod p=(g^(x_A))^(x_B) mod p=y_BA, y_AB=y_BA is used as common secret data to generate an encryption key or the like.
As described above, when DH is executed by using SAC, two modular exponentiations using the same secret information (x_A or x_B) must be performed by SAC. Taking this point into consideration, when the SAC described above is applied to DH, the processing may be vulnerable to an attack explained below.
Assume that the entity A executes a SAC protocol as a client. As a practical SAC method, the protocol RSA-S1 described in the paper by MATSUMOTO et. al will be explained. The client has integers x, d, and n, and intends to obtain y=x^d mod n. d is a secret of the client, and n is open to the public. The Carmichael function of n is represented as λ(n). The process will be described below with reference to FIG. 5.
In step S501, the client randomly generates an integer vector D=[d—1, d—2, . . . , d_M] and a binary vector F=[f—1, f—2, . . . , f_M] such that d=f—1*d—1+f—2*d—2+ . . . +f_M*d_M (mod λ(n)). M and L are some integers, d_i is more than or equal to 1 and less than n, and the weight of F (the number of elements having a value of 1, of the elements f—1, f—2, . . . , f_M of F) is less than or equal to L. The above equation indicates that the residue obtained by dividing d by λ(n) equals the residue obtained by dividing the result of f—1*d—1+f—2*d—2+ . . . +f_M*d_M by λ(n).
In step S502, the client sends n, D, and x to the server.
In step S503, the server computes Z=[z—1, z—2, . . . , z_M] by which z_i=x^(d_i) mod n. In step S504, the server sends Z to the client.
In step S505, the client computes y=y_M as follows. That is, let y—0=1, the client computes y_i=y_(i−1)*z_i mod n if f_i=1, and computes y_i=y_(i−1) if f_i=0, for i=1, 2, . . . , M. The client repeats this computation from i=1 to i=M. That is, the client sequentially obtains y—1, y—2, . . . , and obtains y_M by repeating the computation.
If the modulus n of this protocol is the prime p, λ(n)=λ(p)=p−1, so the protocol can be applied to DH. Accordingly, the client executes the SAC protocol of the modular exponentiation using secret exponent d=x_A twice. The first one is a SAC protocol for obtaining y_A=g^(x_A) mod p, and the second one is a SAC protocol for obtaining y_AB=(y_B)^(x_A) mod p. Since y_A is a value sent to the entity B in IKE executed on the Internet, any attacker (any third party or a SAC server on the Internet) is probably able to obtain the value of y_A. In principle, therefore, this attacker can obtain F which matches the value of y_A by exhaustive search of possible combinations from D and Z. The parameters M and L are so set that the number of possible combinations makes it impossible to obtain F within a practical time. As long as the value of y_A is known, however, it is in principle possible to obtain F (determine at least one combination for y_A).
Assume that an efficient attacking method which breaks the first SAC protocol by exhaustive search is possible in some way. For example, since p and g used in IKE are standardized, a novel distributed algorithm may be found such that each of a large number of computers on the Internet forms a table in which g^i mod p is computed for a number of different i's in advance, and these computers efficiently execute exhaustive search in parallel. If such an attack is possible, as long as the same exponent and the same F are used, the result (y_AB) of the second SAC protocol can be immediately obtained by using D and F which is found by attacking the first SAC protocol. As a consequence, DH is broken. Note that the exhaustive search attack as described above does not hold for the second SAC protocol alone, because in the second SAC protocol the value of the base (y_B) changes every time.
In the method of U.S. Pat. No. 5,046,094 described above, a client itself performs a modular exponentiation by using a secret exponent which the client alone knows. As already pointed out, however, the computation amount is larger than that of RSA-S1 if the security against exhaustive search is equivalent to that of RSA-S1. Accordingly, when this method is applied to DH in which SAC is performed twice, the computation amount also doubles. So, this method does not satisfy the initial purpose (i.e., to allow an apparatus having low computation capability to obtain the result of modular exponentiation without performing any heavy-load computation by itself).
On the other hand, the method of U.S. Pat. No. 5,369,708 described above is the most secure in that no exponent leaks at all, but the computation amount increases. Therefore, when this method is applied to DH in which SAC is performed twice, the computation amount also doubles. So, this method does not satisfy the initial purpose (i.e., to allow an apparatus having low computation capability to obtain the result of modular exponentiation without performing any heavy-load computation by itself).
More specifically, the problems to be solved by the present invention are that SAC by which the amount of computation to be performed by a communication apparatus itself is small has low security, and SAC having high security increases the amount of computation to be performed by a communication apparatus itself.